package SwordFingerOffer;

public class Q12_PathInMatrix {
    //矩阵中的路径
    //矩阵中找单词

    //暴力递归四个方向是行不通的
    //正确做法是枚举每个点的可能性
    public static boolean exist(char[][] board, String word) {
        if (board.length == 0 || word.length() == 0
        || word.length() > board.length * board[0].length){
            return false;
        }
        char[] str = word.toCharArray();

        //某位置是否被使用过
        boolean[][] used = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {

                if (str[0] == board[i][j]){
                    boolean res = process(board, str, 0, i, j, used);
                    if (res){
                        return true;
                    }
                }
            }
        }
        return false;

    }


    public static boolean process(char[][] board, char[] word, int index, int row, int col, boolean[][] used){


        if (index == word.length) {
            return true;
        }
        //错误统一处理 不匹配 | 使用过 | 越界
        if (row < 0 || col < 0 || row == board.length || col == board[0].length || used[row][col] || board[row][col] != word[index]) {
            return false;
        }


        used[row][col] = true;
        //等于但是没把全串匹配完
        //向上
        boolean res = process(board,word, index + 1, row - 1, col, used)
                || process(board,word, index + 1, row + 1, col, used)
                || process(board,word,index + 1, row,col - 1, used)
                || process(board,word, index + 1, row, col + 1, used);
        //恢复现场
        used[row][col] = false;

        return res;
    }


    public static void main(String[] args) {

        char[][] board = new char[][]{  {'A','B','C','E'},
                                        {'S','F','C','S'},
                                        {'A','D','E','E'}};
//        char[][] board = new char[][]{{'a','a'}};
//        String word = "aaa";
        String word = "ABCB";

        boolean exist = exist(board, word);
        System.out.println(exist);
    }
}
